package top.minuy.subject.leetcode.lcp04;

import java.util.*;

/**
 * 匈牙利广度优先遍历
 * LCP 04. 覆盖
 * 你有一块棋盘，棋盘上有一些格子已经坏掉了。你还有无穷块大小为1 * 2的多米诺骨牌，你想把这些骨牌不重叠地覆盖在完好的格子上，请找出你最多能在棋盘上放多少块骨牌？这些骨牌可以横着或者竖着放。
 * <p>
 * <p>
 * <p>
 * 输入：n, m代表棋盘的大小；broken是一个b * 2的二维数组，其中每个元素代表棋盘上每一个坏掉的格子的位置。
 * <p>
 * 输出：一个整数，代表最多能在棋盘上放的骨牌数。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：n = 2, m = 3, broken = [[1, 0], [1, 1]]
 * 输出：2
 * 解释：我们最多可以放两块骨牌：[[0, 0], [0, 1]]以及[[0, 2], [1, 2]]。（见下图）
 * <p>
 * <p>
 * <p>
 * <p>
 * 示例 2：
 * <p>
 * 输入：n = 3, m = 3, broken = []
 * 输出：4
 * 解释：下图是其中一种可行的摆放方式
 * <p>
 * <p>
 * <p>
 * <p>
 * 限制：
 * <p>
 * 1 <= n <= 8
 * 1 <= m <= 8
 * 0 <= b <= n * m
 * 通过次数2,704提交次数7,113
 *
 * @author Minuy
 * @time 9:54
 * @date 2021/11/30
 */
public class SolutionHBFS {
    public int domino(int n, int m, int[][] broken) {

        // 构建整个棋盘，1为坏掉的
        int[][] board = new int[n][m];
        for (int[] ints : broken) {
            board[ints[0]][ints[1]] = 1;
        }

        // 创建图
        GraphDynamic gd = new GraphDynamic();

        // 添加顶点
        int v = m * n;
        for (int i = 0; i < v; i++) {
            gd.addVertex(i);
        }

        // 遍历所有格子
        for (int i = 0; i < n; i++) { // 行
            for (int j = 0; j < m; j++) { // 列
                if (board[i][j] == 0) { // 好格子
                    // 右格子是否相连
                    if (j + 1 < m && board[i][j + 1] == 0) {
                        gd.addEdge((i * m) + j, (i * m) + (j + 1));
                    }
                    // 下格子是否相连
                    if (i + 1 < n && board[i + 1][j] == 0) {
                        gd.addEdge((i * m) + j, ((i + 1) * m) + j);
                    }
                }
            }
        }

        // 二分图最大流最大匹配算法
        return new Hungarian(gd).maxMatching();
    }

    public class Hungarian {

        private GraphDynamic g; // 图
        private int[] matching; // 匹配数组
        private int maxMatching; // 最大匹配值

        public Hungarian(GraphDynamic g) {
            this.g = g;

            BipartitionDetection bd = new BipartitionDetection(g);
            if (!bd.isBipartition()) {
                throw new IllegalArgumentException("BipartiteMatching only works for bipartite graph.");
            }

            maxMatching = 0;
            matching = new int[g.V()];
            Arrays.fill(matching, -1);

            for (int v = 0; v < g.V(); v++) {
                // 没有匹配，并且是这边的
                if (matching[v] == -1 && bd.isBlue(v)) {
                    if (bfs(v)) {
                        maxMatching++;
                    }
                }
            }
        }

        /**
         * 广度优先遍历匹配算法
         *
         * @param s 源点
         * @return boolean 是否匹配成功
         * @author Minuy
         * @date 2021/11/30 8:23
         */
        private boolean bfs(int s) {
            ArrayList<Integer> queue = new ArrayList<>();

            int[] pre = new int[g.V()];
            for (int i = 0; i < matching.length; i++) {
                pre[i] = -1;
            }

            int v = s;
            queue.add(v);
            pre[v] = v;
            while (!queue.isEmpty()) {
                v = queue.remove(0);

                for (String ws : g.adj(v)) {
                    int w = Integer.parseInt(ws);
                    if (pre[w] == -1) {
                        pre[w] = v;
                        // 如果已经匹配过了，继续使用广度优先遍历
                        if (matching[w] != -1) {
                            // 绿色的可以直接跳过，即直接记录对其匹配的点
                            // queue.add(w);
                            queue.add(matching[w]);
                            // pre[w] = v; // 调整到if前面
                            pre[matching[w]] = w;
                        } else { // 找到没有匹配的了，获取路径，调整匹配项
                            // pre[w] = v; // 调整到if前面
                            ArrayList<Integer> path = getAugPath(pre, s, w);
                            // 重新设置匹配项
                            for (int i = 0; i < path.size(); i += 2) {
                                matching[path.get(i)] = path.get(i + 1);
                                matching[path.get(i + 1)] = path.get(i);
                            }
                            return true;
                        }
                    }
                }
            }
            return false;
        }

        /**
         * 找出增广路径
         *
         * @param pre pre数组
         * @param s   源点
         * @param t   目标点
         * @return ArrayList<Integer> 增广路径
         * @author Minuy
         * @date 2021/11/30 8:20
         */
        private ArrayList<Integer> getAugPath(int[] pre, int s, int t) {
            ArrayList<Integer> path = new ArrayList<>();
            int cur = t;
            while (cur != s) {
                path.add(cur);
                cur = pre[cur];
            }
            path.add(s);
            return path;
        }

        /**
         * 获取最大匹配
         *
         * @return int 最大匹配
         * @author Minuy
         * @date 2021/11/29 21:37
         */
        public int maxMatching() {
            return maxMatching;
        }

    }

    /**
     * 检测二分图，深度优先遍历
     *
     * @author Minuy
     * @time 20:21
     * @date 2021/11/19
     */
    public class BipartitionDetection {
        public static final boolean BLUE = true;  // 蓝色
        public static final boolean GREEN = false;  // 绿色

        private GraphDynamic g;
        private boolean[] isVisited;
        private boolean[] colors;
        private boolean isBipartition = true;

        public BipartitionDetection(GraphDynamic g) {
            this.g = g;

            this.isVisited = new boolean[g.V()];

            this.colors = new boolean[g.V()];

            // 遍历所有联通分量
            for (int v = 0; v < g.V(); v++) {
                if (!isVisited[v]) {
                    // 默认给蓝色
                    if (!dfs(v, BLUE)) { // 不是二分图
                        isBipartition = false;
                        break;
                    }
                }
            }
        }

        /**
         * 判断点是否是蓝色的
         *
         * @param v 要被判断的顶点
         * @return boolean
         * @author Minuy
         * @date 2021/11/29 21:18
         */
        public boolean isBlue(int v) {
            g.validateVertex(v);
            return colors[v] == BLUE;
        }

        private boolean dfs(int v, boolean color) {
            isVisited[v] = true;

            colors[v] = color;

            for (String ws : g.adj(v)) {
                int w = Integer.parseInt(ws);
                if (!isVisited[w]) { // 如果没访问过
                    // 染色
                    if (colors[v] == GREEN) {
                        dfs(w, BLUE);
                    } else if (colors[v] == BLUE) {
                        dfs(w, GREEN);
                    }
                } else if (isVisited[w]) { // 如果访问过了，检测冲突
                    if (colors[v] == colors[w]) { // 冲突
                        return false;
                    }
                }
                // 有冗余的检测，没被访问过的是在本节点去赋值的，
                // 所以一定不是冲突的，这里应该是只检测访问过的
            }
            return true;
        }

        /**
         * 给出本图是否是二分图
         *
         * @return boolean 是否是二分图
         * @author Minuy
         * @date 2021/11/19 20:51
         */
        public boolean isBipartition() {
            return isBipartition;
        }
    }

    public class GraphDynamic {
        private int V; // 顶点个数
        private int E; // 边的条数
        private HashMap<String, HashSet<String>> adj; // 邻接矩阵

        public GraphDynamic() {
            adj = new HashMap<>();
        }

        /**
         * 添加一个顶点
         *
         * @param v 顶点名
         * @author Minuy
         * @date 2021/11/30 9:45
         */
        public void addVertex(int v) {
            addVertex(String.valueOf(v));
        }

        /**
         * 添加一个顶点
         *
         * @param v 顶点名
         * @author Minuy
         * @date 2021/11/30 9:45
         */
        public void addVertex(String v) {
            adj.put(v, new HashSet<>());
            V++;
        }

        /**
         * 添加一条边
         *
         * @param v 起始顶点
         * @param w 结束顶点
         * @author Minuy
         * @date 2021/11/30 9:46
         */
        public void addEdge(int v, int w) {
            addEdge(String.valueOf(v), String.valueOf(w));
        }

        /**
         * 添加一条边
         *
         * @param v 起始顶点
         * @param w 结束顶点
         * @author Minuy
         * @date 2021/11/30 10:01
         */
        public void addEdge(String v, String w) {
            if (hasEdge(v, w)) {
                throw new IllegalArgumentException(
                        String.format("Edge %s-%s is existent.", v, w));
            }

            if (v.equals(w)) {
                // 自环，不允许出现在简单图中
                throw new IllegalArgumentException("Self Loop is Detected.");
            }
            if (adj.get(v).contains(w)) {
                // 平行边，不允许出现在简单图中
                throw new IllegalArgumentException("Parallel Edges are Detected.");
            }

            // 连接两个顶点
            adj.get(v).add(w);

            adj.get(w).add(v); // 无向图的表示是两边都相连的


            E++;
        }

        /**
         * 验证顶点序号的合法性
         *
         * @param v 顶点值
         * @author Minuy
         * @date 2021/11/15 17:26
         */
        public void validateVertex(int v) {
            validateVertex(String.valueOf(v));
        }

        /**
         * 验证顶点名字的合法性
         *
         * @param v 顶点名字
         * @author Minuy
         * @date 2021/11/30 9:49
         */
        public void validateVertex(String v) {
            if (!adj.containsKey(v)) {
                throw new IllegalArgumentException("Vertex " + v + " is non-existent.");
            }
        }

        /**
         * 只读，边的数量
         *
         * @return int 边的数量
         * @author Minuy
         * @date 2021/11/15 17:35
         */
        public int E() {
            return E;
        }

        /**
         * 只读，顶点的数量
         *
         * @return int 顶点的数量
         * @author Minuy
         * @date 2021/11/15 17:35
         */
        public int V() {
            return V;
        }

        /**
         * 验证两个顶点之间是否有边
         *
         * @param v 顶点1的序号
         * @param w 顶点2的序号
         * @return boolean 有无边
         * @author Minuy
         * @date 2021/11/15 17:38
         */
        public boolean hasEdge(int v, int w) {
            return hasEdge(String.valueOf(v), String.valueOf(w));
        }

        /**
         * 验证两个顶点之间是否有边
         *
         * @param v 顶点1的序号
         * @param w 顶点2的序号
         * @return boolean 有无边
         * @author Minuy
         * @date 2021/11/30 10:20
         */
        public boolean hasEdge(String v, int w) {
            return hasEdge(v, String.valueOf(w));
        }

        /**
         * 验证两个顶点之间是否有边
         *
         * @param v 顶点1的序号
         * @param w 顶点2的序号
         * @return boolean 有无边
         * @author Minuy
         * @date 2021/11/30 10:20
         */
        public boolean hasEdge(int v, String w) {
            return hasEdge(String.valueOf(v), w);
        }

        /**
         * 验证两个顶点之间是否有边
         *
         * @param v 顶点1的名字
         * @param w 顶点2的名字
         * @return boolean 有无边
         * @author Minuy
         * @date 2021/11/30 9:57
         */
        public boolean hasEdge(String v, String w) {
            validateVertex(v);
            validateVertex(w);
            return adj.get(v).contains(w);
        }

        /**
         * 返回与顶点v相邻的所有顶点
         *
         * @param v 顶点v
         * @return Iterable<String> 与顶点v相邻的所有顶点
         * @author Minuy
         * @date 2021/11/15 19:55
         */
        public Iterable<String> adj(int v) {
            return adj(String.valueOf(v));
        }

        /**
         * 返回与顶点v相邻的所有顶点
         *
         * @param v 顶点v
         * @return Iterable<String> 与顶点v相邻的所有顶点
         * @author Minuy
         * @date 2021/11/30 10:04
         */
        public Iterable<String> adj(String v) {
            validateVertex(v);
            return adj.get(v);
        }

        /**
         * 获取顶点v的度
         *
         * @param v 顶点v
         * @return int 顶点v的度
         * @author Minuy
         * @date 2021/11/15 17:46
         */
        public int degree(int v) {
            // 对于有向图的度，分为出度和入度
            return degree(String.valueOf(v));
        }

        /**
         * 获取顶点v的度
         *
         * @param v 顶点v
         * @return int 顶点v的度
         * @author Minuy
         * @date 2021/11/30 10:05
         */
        public int degree(String v) {
            validateVertex(v);
            return adj.get(v).size();
        }
    }
}
